package ext;

import utils.ArrayUtils;

import java.util.Arrays;

/**
 * 土地划分
 */
public class Partition {
    public int[] getPartition(int[][] land, int n, int m) {
        int[] A = new int[n + 1];
        int[] B = new int[n + 1];
        int[] C = new int[n + 1];

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (land[i][j] == 1)
                    A[j + 1]++;
                else
                    B[j]++;
            }
        }


        System.out.println(Arrays.toString(A));
        System.out.println(Arrays.toString(B));

        for (int i = 1; i <=n; ++i)
            A[i] = A[i] + A[i - 1];

        for (int i = n - 2; i >= 0; --i)
            B[i] = B[i] + B[i + 1];

        System.out.println(Arrays.toString(A));
        System.out.println(Arrays.toString(B));

        int min = Integer.MAX_VALUE;
        int idx = -1;
        for (int i = 0; i < n + 1; ++i) {
            C[i] = A[i] + B[i];
            if (C[i] < min) {
                min = C[i];
                idx = i;
            }
        }

        return new int[]{idx, idx + 1};
    }

    public static void main(String[] args) {
        int[][] land = {{1, 1, 1, 1}, {0, 0, 0, 0}, {1, 0, 1, 1}};
        Partition p = new Partition();
        System.out.println(Arrays.toString(p.getPartition(land,4,3)));
    }
}
